/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <list>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* getmid(ListNode* cur)
    {
        ListNode* fast = cur;
        ListNode* slow = cur;
        while(fast->next->next&&fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* next= slow->next;
        slow->next = nullptr;//将这两段链表分开完成分治
        return next;//再返回中间点
    }//这个函数的目的是找到这个链表的中间节点
    ListNode* merge(ListNode* left,ListNode* right)
    {
        //将两个链表进行合并
        ListNode* newhead = new ListNode(0);
        ListNode* cur = newhead;
        while(left&&right)
        {
            if(left->val<right->val)
            {
                cur->next = left;
                left = left->next;
            }
            else 
            {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        if(left)
        {
            cur->next = left;
        }
        if(right)
        {
            cur->next = right;
        }
        ListNode* ret = newhead->next;
        delete newhead;
        return ret;
    }
    ListNode* mergesort(ListNode* head)
    {
        if(head == nullptr)
        {
            return nullptr;
        }
        if(head->next == nullptr)
        {
            return head;//这个节点已经是一个节点了
        }
        ListNode* mid = getmid(head);
        ListNode* newleft = mergesort(head);
        ListNode* newright = mergesort(mid);
        //现在newleft和newright就是两个链表了，我需要完成合并
        return merge(newleft,newright);
    }
    ListNode* sortInList(ListNode* head) 
    {
        return mergesort(head);    
    }
};